package com.wx.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @desc: 有多少小于当前数字的数字
 * 给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
 * 换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
 * 以数组形式返回答案。
 * @author: wx
 * @time: 2020/4/14 6:07 PM
 */
public class SmallerNumbersThanCurrentTopic {
    
    
    /**
     * 暴力解法
     */
    public static int[] smallerNumbersThanCurrent(int[] nums) {

        if (nums == null || nums.length == 0) {
            return new int[0];
        }

        int[] tmep = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[i]) {
                    tmep[i]++;
                } else if (nums[j] > nums[i]) {
                    tmep[j]++;
                }
            }

        }
        return tmep;
    }
    
    /**
     * 排序+map解法
     */
    public static int[] smallerNumbersThanCurrentV2(int[] nums) {

        if (nums == null || nums.length == 0) {
            return new int[0];
        }

        int[] copyArray = Arrays.copyOf(nums, nums.length);
        Arrays.sort(copyArray);
        Map<Integer,Integer> countMap = new HashMap<>();
        for (int i = 0; i < copyArray.length; i++) {
            int num = copyArray[i];
            if (!countMap.containsKey(num)) {
                countMap.put(num,i);
            }
        }

        int[] tmep = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            tmep[i] = countMap.get(nums[i]);
        }
        return tmep;
    }


    public static void main(String args[]) {
        int[] nums = new int[]{6, 5, 4, 8};
        System.out.println(Arrays.toString(smallerNumbersThanCurrentV2(nums)));
    }


}
